#include <cstdio>
#include <algorithm>
using namespace std;
long long pow_mod(long long a,long long b,long long m){
    long long res=1;
    a%=m;
    while(b){
        if(b%2){
            res=(res*a)%m;
        }
        b/=2;
        a=(a*a)%m;
    }
    return res;
}
int main(void){
    int t;
    long long a,b,m;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&a,&b,&m);
        printf("%lld\n",pow_mod(a,b,m));
    }
    return 0;
}
